Back to course home
0% completed
Vote For New Content
Analyzing Recursive Algorithms
Introduction to Recursion
Recursion Tree Method
Recurrence Relation Method
Master Theorem Method
Space Complexity Analysis of Recursive Algorithm
Logarithmic Time and Space: O(log n)
Linearithmic Time: O(n log n)
Exponential Time and Space: O(2ⁿ)
Quiz
Data Structures and Complexity Analysis
Array
Linked List
Hash Table and Set
Stack and Queue
Binary Search Tree
Quiz
Practical Applications and Case Studies
Sorting Algorithms
Graph Algorithms
Dynamic Programming Algorithms
Coding Interview Problems
Trade-offs in Algorithm Design
Quiz
Question 1
Which of the following statements is true about space complexity?
A
Space complexity only considers the space taken by input variables.
B
Space complexity measures the total memory used by an algorithm, including output, and auxiliary space.
C
Space complexity is independent of the input size.
D
Space complexity is only important for recursive algorithms.
Question 2
What is auxiliary space?
A
The space taken by the input itself.
B
Extra space or temporary space used by an algorithm, excluding the input.
C
The total space taken by an algorithm, including input.
D
The space taken by the output of an algorithm.
Question 3
What is the space complexity of the following code?
public void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
A
O(1)
B
O(n)
C
O(n2)
D
O(log n)
Question 4
What is the space complexity of the following recursive function?
public int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}
A
O(1)
B
O(log n)
C
O(n2)
D
O(n)
Question 5
Analyze the space complexity of the following code:
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n; j++) {
dp[0][j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
A
O(m * n)
B
O(m + n)
C
O(n)
D
O(1)
Question 6
What is the space complexity of the following code?
public int[] calculatePrefixSum(int[] arr) {
int[] prefixSum = new int[arr.length];
prefixSum[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
return prefixSum;
}
A
O(1)
B
O(n2)
C
O(n)
D
O(log n)
Quadratic Space: O(n²)
Introduction to Recursion
Mark as Completed
On this page